/* Copyright (c) 2006 by M Aamir Maniar 
 * 
 * Permission is hereby granted, free of charge, to any person obtaining 
 * a copy of this software and associated documentation files (the 
 * "Software"), to deal in the Software without restriction, including 
 * without limitation the rights to use, copy, modify, merge, publish, 
 * distribute, sublicense, and/or sell copies of the Software, and to 
 * permit persons to whom the Software is furnished to do so, subject to 
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be 
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 * 
 * */

namespace Generic.DataStructures.Trees
{
	using System;
	using System.Collections.Generic;
	using System.Text;

    //TODO:Not complete code
    public class BinaryTreeNode<T>: IComparable<BinaryTreeNode<T>>, IEqualityComparer<BinaryTreeNode<T>>
    {
        public BinaryTreeNode()
        {
		}

        public BinaryTreeNode(T value)
        {
            Value = value;//Find ParentNode
        }

        private T _value;
        public T Value
        {
            get { return _value; }
            set { _value = value; }
        }

        private BinaryTreeNode<T> _leftChild;
        public BinaryTreeNode<T> LeftChild
        {
            get { return _leftChild; }
            set { _leftChild = value; }
        }

        private BinaryTreeNode<T> _rightChild;
        public BinaryTreeNode<T> RightChild
        {
            get { return _rightChild; }
            set { _rightChild = value;}
        }

        private BinaryTreeNode<T> _parent;
        public BinaryTreeNode<T> Parent
        {
            get { return _parent; }
            set { _parent = value; }
        }

        private BinaryTree<T> _binaryTree = null;
        public BinaryTree<T> BinaryTree
        {
            get { return _binaryTree; }
            set { _binaryTree = value; }
        }

        public bool IsLeafNode
        {
            get 
            {
                return (_rightChild == null && _leftChild == null);
            }
        }

        public BinaryTreeNode<T> FindMinimum()
        {
            BinaryTreeNode<T> tempNode = this;
            while (tempNode != null)
            {
                tempNode = tempNode.LeftChild;
            }
            return tempNode;
        }

        #region IComparable Members

        /// <summary>
        /// Compares the current object with another object of the same type.
        /// </summary>
        /// <param name="other">An object to compare with this object.</param>
        /// <returns>
        /// A 32-bit signed integer that indicates the relative order of the objects being compared. The return value has the following meanings: Value Meaning Less than zero This object is less than the other parameter.Zero This object is equal to other. Greater than zero This object is greater than other.
        /// </returns>
        int IComparable<BinaryTreeNode<T>>.CompareTo(BinaryTreeNode<T> other)
        {
            return CompareTo(other);
        }

        public int CompareTo(T otherValue)
        {
            if (_comparison != null)
            {
                return _comparison(_value, otherValue);
            }

            if (_comparer != null)
            {
                return _comparer.Compare(_value, otherValue);
            }

            if (_value is IComparable<T>)
            {
                return ((IComparable<T>)_value).CompareTo(otherValue);
            }

            if (_value is IComparable)
            {
                return ((IComparable)_value).CompareTo(otherValue);
            }
            throw new InvalidOperationException("Node is not comparable, please supply IComparer<T> to make it comparable.");

        }

        public int CompareTo(BinaryTreeNode<T> otherNode)
        {
            return CompareTo(otherNode.Value);
        }

        #endregion

        private IComparer<T> _comparer;
        public IComparer<T> Comparer
        {
            get { return _comparer; }
            set { _comparer = value; }
        }

        private Comparison<T> _comparison;
        public Comparison<T> Comparison
        {
            get { return _comparison; }
            set { _comparison = value; }
        }

        #region Overrides
        public override string ToString()
        {
            return "BinaryTreeNode: " + Value.ToString();
        }

        public override int GetHashCode()
        {
            return _value.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            return this.Equals(this, (BinaryTreeNode<T>)obj);
        }
        #endregion

        #region Operators
        public static bool operator <(BinaryTreeNode<T> node1, BinaryTreeNode<T> node2)
        {

            return node1.CompareTo(node2) < 0;
        }

        public static bool operator >(BinaryTreeNode<T> node1, BinaryTreeNode<T> node2)
        {
            return node1.CompareTo(node2) > 0;
        }

        public static bool operator ==(BinaryTreeNode<T> node1, BinaryTreeNode<T> node2)
        {
            if (object.ReferenceEquals(node1, node2))
                return true;
            else if (object.ReferenceEquals(node1, null) || object.ReferenceEquals(node2, null))
                return false;
            return node1.CompareTo(node2) == 0;
        }

        public static bool operator !=(BinaryTreeNode<T> node1, BinaryTreeNode<T> node2)
        {
            return !(node1 == node2);
        }

        public static bool operator <=(BinaryTreeNode<T> node1, BinaryTreeNode<T> node2)
        {
            return node1.CompareTo(node2) <= 0;
        }

        public static bool operator >=(BinaryTreeNode<T> node1, BinaryTreeNode<T> node2)
        {
            return node1.CompareTo(node2) >= 0;
        }

        #endregion


        #region IEqualityComparer<BinaryTreeNode<T>> Members

        public bool Equals(BinaryTreeNode<T> x, BinaryTreeNode<T> y)
        {
            if (x == null && y == null)
                return true;
            if ((x == null && y != null) || (x != null && y == null))
                return false;
            return x.CompareTo(y) == 0;
        }

        public int GetHashCode(BinaryTreeNode<T> obj)
        {
            return obj.Value.GetHashCode();
        }

        #endregion

        public static int CalculateExactDepth(BinaryTreeNode<T> node, int nodeDepth)
        {
            if (node == null)
                return 0;
            return nodeDepth + Math.Max(CalculateExactDepth(node.LeftChild, nodeDepth), CalculateExactDepth(node.RightChild, nodeDepth));
        }
    }

    public class BinaryTreeNodeDepth<T>
    {
        BinaryTree<T> _binaryTree;

        public BinaryTreeNodeDepth(BinaryTree<T> binaryTree)
        {
            _binaryTree = binaryTree;
        }

        public double Maximum
        {
            get { return _binaryTree.Count -1; }
        }

        public double Minimum
        {
            get
            {
                return Math.Floor(Math.Log(_binaryTree.Count, 2));
            }
        }

    }
}
